package com.example.arithmeticleetcode.learnArithmetic.graph;


import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-11-17 10:47
 **/
public class ListGraph<V, E> extends Graph<V, E> {

    private Map<V, Vertex<V, E>> vertics = new HashMap<>();
    private Set<Edge<V, E>> edges = new HashSet<>();
    private Comparator<Edge<V, E>> edgeComparator = (e1, e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };

    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }

    public ListGraph() {
    }

    public void print() {
        System.out.println("顶点----------------------------");
        vertics.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("out---------");
            System.out.println(vertex.outEdges);
            System.out.println("in----------");
            System.out.println(vertex.inEdges);
        });
        System.out.println("边=========================");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });

    }

    @Override
    public int edgesSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertics.size();
    }

    @Override
    public void addVertext(V v) {
        if (vertics.containsKey(v)) return;
        vertics.put(v, new Vertex<>(v));

    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        //判断from to 定点是否存在
        Vertex<V, E> fromVertex = vertics.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertics.put(from, fromVertex);
        }

        Vertex<V, E> toVertex = vertics.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertics.put(to, toVertex);
        }


        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        edge.weight = weight;
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }

        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);

        edges.add(edge);


    }

    @Override
    public void removeVertext(V v) {
        Vertex<V, E> vertex = vertics.get(v);
        if (vertex == null) return;
        Iterator<Edge<V, E>> outIterator = vertex.outEdges.iterator();
        while (outIterator.hasNext()) {
            Edge<V, E> edge = outIterator.next();
            edge.to.inEdges.remove(edge);
            //将当前遍历到的元素从当前集合vertex.outEdges中删除掉
            outIterator.remove();
            edges.remove(edge);
        }

        Iterator<Edge<V, E>> inIterator = vertex.inEdges.iterator();
        while (inIterator.hasNext()) {
            Edge<V, E> edge = inIterator.next();
            edge.from.outEdges.remove(edge);
            //将当前遍历到的元素从当前集合vertex.inEdges中删除掉
            inIterator.remove();
            edges.remove(edge);
        }


    }

    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertics.get(from);
        if (fromVertex == null) return;
        Vertex<V, E> toVertex = vertics.get(to);
        if (toVertex == null) return;
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(toVertex);
            edges.remove(edge);
        }
    }

    @Override
    public void bfs(V begin, VertexVisitor<V> vertexVisitor) {
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return;

        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();

        queue.offer(beginVertex);
        visitedVertices.add(beginVertex);

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            if (vertexVisitor.visit(vertex.value)) return;

            for (Edge<V, E> edge : vertex.outEdges) {
                if (visitedVertices.contains(edge.to)) continue;
                queue.offer(edge.to);
                visitedVertices.add(edge.to);
            }
        }

    }

    @Override
    public void dfs(V begin, VertexVisitor<V> vertexVisitor) {
        if (vertexVisitor == null) return;
        Vertex<V, E> beginVertex = vertics.get(begin);
        if (beginVertex == null) return;

        Stack<Vertex<V, E>> stack = new Stack<>();
        Set<Vertex<V, E>> vertexVisited = new HashSet<>();

        stack.push(beginVertex);
        vertexVisited.add(beginVertex);
        if (vertexVisitor.visit(beginVertex.value)) return;

        while (!stack.isEmpty()) {
            Vertex<V, E> vertex = stack.pop();
            for (Edge<V, E> edge : vertex.outEdges) {
                if (vertexVisited.contains(edge.to)) continue;
                vertexVisited.add(edge.to);
                stack.push(edge.from);
                stack.push(edge.to);
                if (vertexVisitor.visit(edge.to.value)) return;
                break;
            }
        }
    }

    @Override
    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Map<Vertex<V, E>, Integer> map = new HashMap<>();
        //初始化 将度为0的节点放入队列
        vertics.forEach((v, vertex) -> {
            if (vertex.inEdges.size() == 0) {
                queue.add(vertex);
            } else {
                map.put(vertex, vertex.inEdges.size());
            }

        });

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            list.add(vertex.value);
            for (Edge<V, E> edge : vertex.outEdges) {
                Integer count = map.get(edge.to) - 1;
                if (count == 0) {
                    queue.offer(edge.to);
                } else {
                    map.put(edge.to, count);
                }
            }
        }

        return list;
    }

    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return prim();
    }

    private Set<EdgeInfo<V, E>> prim() {
        Iterator<Vertex<V, E>> iterator = vertics.values().iterator();
        if (!iterator.hasNext()) return null;
        Vertex<V, E> vertex = iterator.next();

        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        Set<Vertex<V, E>> addedVertices = new HashSet<>();
        addedVertices.add(vertex);
        //
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);

        int edgeSize = vertics.size();
        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            Edge<V, E> edge = heap.remove();
            if (addedVertices.contains(edge.to)) continue;

            edgeInfos.add(edge.info());
            addedVertices.add(edge.to);
            heap.addAll(edge.to.outEdges);
        }

        //相当于最小堆 nlog(n)
//        PriorityQueue<Edge<V, E>> heap = new PriorityQueue<>((e1, e2) -> {
//            return 0;
//        });
//
//        for (Edge<V, E> edge : vertex.outEdges) {
//
//        }
        return edgeInfos;
    }

    private Set<EdgeInfo<V, E>> kruskal() {
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);

        int edgeSize = vertics.size() - 1;

        while (!heap.isEmpty() && edgeInfos.size() <= edgeSize) {

        }
        return edgeInfos;
    }

    //    @Override
//    public void bfs(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return;
//
//        Queue<Vertex<V, E>> queue = new LinkedList<>();
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//
//        queue.offer(beginVertex);
//        visitedVertices.add(beginVertex);
//
//        while (!queue.isEmpty()) {
//            Vertex<V, E> vertex = queue.poll();
//            System.out.println(vertex.value);
//
//            for (Edge<V, E> edge : vertex.outEdges) {
//                if (visitedVertices.contains(edge.to)) continue;
//                queue.offer(edge.to);
//                visitedVertices.add(edge.to);
//            }
//        }
//    }
//
//    @Override
//    public void dfs(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return;
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//        Stack<Vertex<V, E>> stack = new Stack<>();
//        stack.push(beginVertex);
//        visitedVertices.add(beginVertex);
//        System.out.println(beginVertex.value);
//        while (!stack.isEmpty()) {
//            Vertex<V, E> vertex = stack.pop();
//            for (Edge<V, E> edge : vertex.outEdges) {
//                if (visitedVertices.contains(edge.to)) continue;
//                stack.push(edge.from);
//                stack.push(edge.to);
//                System.out.println(edge.to.value);
//                visitedVertices.add(edge.to);
//                break;
//            }
//        }
//    }
//
//    public void dfs2(V begin) {
//        Vertex<V, E> beginVertex = vertics.get(begin);
//        if (beginVertex == null) return;
//        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
//        dfs2(beginVertex, visitedVertices);
//    }
//
//    private void dfs2(Vertex<V,E> vertex, Set<Vertex<V, E>> visitedVertices) {
//
//        System.out.println(vertex.value);
//        visitedVertices.add(vertex);
//
//        for (Edge<V, E> edge : vertex.outEdges) {
//            if (visitedVertices.contains(edge.to)) continue;
//            dfs2(edge.to, visitedVertices);
//        }
//    }

    private static class Vertex<V, E> {
        V value;
        Set<Edge<V, E>> inEdges = new HashSet<>();
        Set<Edge<V, E>> outEdges = new HashSet<>();

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    //E必须具备可比较性 E extends Comparable<E>
    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        EdgeInfo<V, E> info() {
            return new EdgeInfo<>(from.value, to.value, weight);
        }

        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode() * 31;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }


}
